/**
 * 描述：leetcode203移除链表元素
 *
 * @author WangB
 * @create 2018-10-20-16:17
 */
public class Solution203{

    /**
     * 非递归版
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.val==val)
            {
                prev.next = prev.next.next;
            }
            else
                prev = prev.next;
        }

        return dummyHead.next;
    }

    /**
     * 递归版
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements1(ListNode head, int val) {

    if(head==null) return null;
    head.next = removeElements ( head.next,val );
    if(head.val == val)
        return head.next;
    else
        return head;


    }


    public static void main(String[] args){
        int[] arr = new int[]{1,4,2,2,43,453,43};
        ListNode head = new ListNode ( arr );
        System.out.println ( head );
        (new Solution203 ()).removeElements1 ( head,4 );
        System.out.println ( head );
    }
}
 class ListNode{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    /**
     * 添加了一个构造函数，用来接收一个数组，并将其转换成以当前节点为头节点的链表
     * @param arr
     */
    public ListNode(int[] arr){
        if(arr.length == 0 || arr==null)
            throw new IllegalArgumentException ( "数组是空的" );

        this.val = arr[0];
        ListNode cur = this;
        for ( int i = 1 ; i < arr.length ; i++ ) {
            cur.next= new ListNode ( arr[i] );
            cur = cur.next;
        }


    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder ();
        ListNode cur = this;
        while(cur!=null){
            res.append ( cur.val +"->");
            cur = cur.next;
        }
        res.append ( "NULL" );
        return res.toString ();
    }


}